package wells.tree;

public class AVLTree {
	private Node root;

	public void insert(int value) {

		root = insert(root, value);
	}

	private Node insert(Node x, int value) {
		if (x == null) {// 首次插入
			return new Node(value, 1);
		}
		int xVal = x.value;

		if (value < xVal) {
			x.left = insert(x.left, value);

			if (getHeight(x.left) - getHeight(x.right) > 1) {// left
				if (getHeight(x.left.left) > getHeight(x.left.right)) {// left
					x = leftLeftRotation(x);
				} else {
					x = leftRightRotation(x);

				}
			}

		} else if (value > xVal) {
			x.right = insert(x.right, value);

			if (getHeight(x.right) - getHeight(x.left) > 1) {// right
				if (getHeight(x.right.right) > getHeight(x.right.left)) {// right
					x = rightRightRotation(x);
				} else {
					x = rightLeftRotation(x);
				}
			}
		} else {
			// 重复数据 do nothing
		}

		x.height = reCalcHeight(x);

		return x;

	}

	public Node select(int value) {
		return select(root, value);// work when BST is empty
	}

	private Node select(Node x, int value) {

		if (x == null)
			return null;

		int xVal = x.value;

		if (value < xVal)
			return select(x.left, value);
		else if (value > xVal)
			return select(x.right, value);
		else
			return x;
	}

	public void delete(int value) {
		root = delete(root, value);
	}

	private Node delete(Node x, int value) {

		if (x == null) {
			return null;
		}

		int xVal = x.value;

		if (value < xVal)
			x.left = delete(x.left, value);// 左子树
		else if (value > xVal)
			x.right = delete(x.right, value);// 右子树
		else {
			if (x.right == null) {
				return x.left;
			}
			if (x.left == null) {
				return x.right;
			}

			Node temp = x;// 要被删除的节点，先拿着
			x = min(temp.right); // 获取右子树最小的节点
			x.right = deleteMin(temp.right);// 删除右子树最小节点，并将删除后的树作为x的右子树
			x.left = temp.left;// 原来的左子树保持，作为新根节点的左子树
		}

		// 删除完成，调整平衡性
		x.height = reCalcHeight(x);
		
		// 失衡
		if (getHeight(x.left) - getHeight(x.right) >= 2) {
			// 删除发生在右子树，模拟插入发生在左子树
			if (getHeight(x.left.left) > getHeight(x.left.right)) {
				// 插入发生在左子树，LL旋转
				return leftLeftRotation(x);
			} else {
				// LR旋转
				return leftRightRotation(x);
			}
		} else if (getHeight(x.left) - getHeight(x.right) <= -2) {
			// 删除发生在左子树，模拟插入发生在右子树
			if (getHeight(x.right.left) > getHeight(x.right.right)) {
				// RL旋转
				return rightLeftRotation(x);
			} else {
				// RR旋转
				return rightRightRotation(x);
			}
		}
		// 未失衡，不做操作
		return x;
	}

	private Node min(Node x) {
		if (x.left == null)
			return x;
		return min(x.left);
	}

	private Node deleteMin(Node x) {

		if (x.left == null)
			return x.right;

		x.left = deleteMin(x.left);

		return x;
	}

	private int getHeight(Node n) {
		if (n == null) {
			return 0;
		}
		return n.height;
	}

	private int reCalcHeight(Node x) {
		return Math.max(getHeight(x.left), getHeight(x.right)) + 1;
	}

	private Node leftLeftRotation(Node x) {// LL旋转
		Node left = x.left;
		x.left = left.right;
		left.right = x;
		x.height = reCalcHeight(x);// 挂了新的子节点，重新计算高度
		left.height = reCalcHeight(left);// 挂了新的子节点，重新计算高度
		return left;
	}

	private Node rightRightRotation(Node x) {// RR旋转
		Node right = x.right;
		x.right = right.left;
		right.left = x;
		x.height = reCalcHeight(x);// 挂了新的子节点，重新计算高度
		right.height = reCalcHeight(right);// 挂了新的子节点，重新计算高度
		return right;
	}

	private Node leftRightRotation(Node x) {// LR旋转，先将左儿子RR旋转，再将根节点LL旋转
		x.left = rightRightRotation(x.left);
		return leftLeftRotation(x);
	}

	private Node rightLeftRotation(Node x) {// RL旋转，先将右儿子LL旋转，再将根节点RR旋转
		x.right = leftLeftRotation(x.right);
		return rightRightRotation(x);
	}

	private class Node {

		private int value;
		private Node left;
		private Node right;
		private int height;

		public Node(int value, int height) {
			super();
			this.height = height;
			this.value = value;
			left = right = null;
		}

		@Override
		public String toString() {
			return +value + "=>{" + left + "," + right + "}";
		}
	}

	@Override
	public String toString() {
		return "" + root;
	}
}
